package com.sheng.leetcode.year2022.swordfingeroffer.day29;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/29
 *<p>
 * 剑指 Offer 49. 丑数<p>
 *<p>
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。<p>
 * 求按从小到大的顺序的第 n 个丑数。<p>
 *<p>
 * 示例:<p>
 * 输入: n = 10<p>
 * 输出: 12<p>
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。<p>
 *<p>
 * 说明:<p>
 * 1是丑数。<p>
 * n不超过1690。<p>
 * 注意：本题与主站 264 题相同：<a href="https://leetcode-cn.com/problems/ugly-number-ii/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/chou-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0049 {

    @Test
    public void test01() {
        int n = 10;
        System.out.println(new Solution49().nthUglyNumber(n));
    }
}
class Solution49 {
    public int nthUglyNumber(int n) {
        // 多路归并
        int i2 = 1, i3 = 1, i5 = 1;
        int[] nums = new int[n + 1];
        nums[1] = 1;
        for (int i = 2; i <= n; i++) {
            int a = nums[i2] * 2, b = nums[i3] * 3, c = nums[i5] * 5;
            int min = Math.min(a, Math.min(b, c));
            if (min == a) {
                i2++;
            }
            if (min == b) {
                i3++;
            }
            if (min == c) {
                i5++;
            }
            nums[i] = min;
        }
        return nums[n];
    }
}
